package NTree;

import java.util.*;

/*
N 叉树的前序遍历
给定一个 n叉树的根节点 root，返回 其节点值的 前序遍历 。
n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：[1,3,5,6,2,4]
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/n-ary-tree/x0locc/
 */

public class _11N叉树的前序遍历 {
    public static void main(String[] args) {

    }

    class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }

    //DFS
    //传递集合版
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }

    public void dfs(Node root, List<Integer> preorder) {
        if (root == null) {
            return;
        }
        preorder.add(root.val);
        for (Node child : root.children) {
            dfs(child, preorder);
        }
    }

    //官解：迭代
    //相比于二叉树的遍历，多个Hashmap对已经遍历过的结点进行标记，已获得下个孩子的index
//    链接：https://leetcode.cn/problems/n-ary-tree-preorder-traversal/solutions/1317175/n-cha-shu-de-qian-xu-bian-li-by-leetcode-bg99/
    class Solution {
        public List<Integer> preorder(Node root) {
            List<Integer> res = new ArrayList<Integer>();
            if (root == null) {
                return res;
            }
            Map<Node, Integer> map = new HashMap<Node, Integer>();
            Deque<Node> stack = new ArrayDeque<Node>();
            Node node = root;
            while (!stack.isEmpty() || node != null) {
                while (node != null) {
                    res.add(node.val);
                    stack.push(node);
                    List<Node> children = node.children;
                    if (children != null && children.size() > 0) {
                        map.put(node, 0);
                        node = children.get(0);
                    } else {
                        node = null;
                    }
                }
                node = stack.peek();
                int index = map.getOrDefault(node, -1) + 1;
                List<Node> children = node.children;
                if (children != null && children.size() > index) {
                    map.put(node, index);
                    node = children.get(index);
                } else {
                    stack.pop();
                    map.remove(node);
                    node = null;
                }
            }
            return res;
        }
    }

}
